/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void _ConvertList(TreeNode *pRootOfTree, TreeNode *&prev){
		if(nullptr == pRootOfTree)
			return;

        // 中序遍历就是有序
		_ConvertList(pRootOfTree->left, prev);

		/*想象一下，上面三行代码就是用来递归左子树的，直到左子树是空才返回，执行下面的代码时就是4这个节点了*/

		TreeNode *cur = pRootOfTree;	// 记录当前位置
		cur->left = prev;				// 当前位置比如是4，4也是这棵树(二叉搜索树)最小的值，此时prev还是nullptr

		if(prev != nullptr)				// 当pRootOfTree是4时,此时prev还是nullptr,等到递归返回退的时候才是4
			prev->right = cur;

		prev = cur;						// 此时要递归4的右子树了，4的右子树是空，就返回了

		_ConvertList(pRootOfTree->right, prev);

		// 当pRootOfTree是4时，代码走到这执行完了，返回去就回到6这个节点去了，到那时prev就不是nullptr了，就是4这个节点了
	}


    TreeNode* Convert(TreeNode* pRootOfTree) {
		// 注意题目只是说双向链表，没有说双向循环列表

		TreeNode *prev = nullptr;		// 需要一个 prev 和 cur 记录
		_ConvertList(pRootOfTree, prev);

		// 此时链表已经转换好了，找头节点
		TreeNode *head = pRootOfTree;
		while(head && head->left)
		{
			head = head->left;
		}
		return head;
    }
};
